#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/8/23 22:39
# @Author  : Yuyun
# @File    : leetcode_15_三数之和.py
# @IDE     : PyCharm

"""
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
"""

class Solution:
    def sum_of_three(self, nums, target):
        result = []     #   存储结果数组[a, b, c]
        length =len(nums)
        nums.sort()     #   升序排序
        for start in range(length):
            #   如果数组最小值 > 目标值，表示（正整数）数组无法找到三元组
            if (nums[start] > target) and (target >= 0 or nums[start] >= 0):
                return result
            #   a值去重，取一次，后续相同值不取
            if start > 0 and nums[start] == nums[start - 1]:
                continue
            mid = start + 1
            end = length - 1
            while mid < end:
                total = nums[start] + nums[mid] + nums[end]
                if total > target:
                    end -= 1
                elif total < target:
                    mid += 1
                else:       #找到三元组
                    result.append([nums[start], nums[mid], nums[end]])
                    mid += 1
                    end -= 1
        return result
if __name__ == '__main__':
    nums = list(map(int, input().split(',')))
    solution = Solution()
    print(solution.sum_of_three(nums, 0))
